package com.lw.leetcode.greedy.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1691. 堆叠长方体的最大高度
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/10 11:34
 */
public class MaxHeight {

    public int maxHeight(int[][] cuboids) {
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }
        Arrays.sort(cuboids, (a, b) -> a[0] == b[0] ? (a[1] == b[1] ? Integer.compare(b[2], a[2]) :
                Integer.compare(b[1], a[1])) : Integer.compare(b[0], a[0]));
        int length = cuboids.length;
        int[] arr = new int[length];
        arr[0] = cuboids[0][2];
        int max = arr[0];
        for (int i = 1; i < length; i++) {
            int[] item = cuboids[i];
            int h = 0;
            for (int j = 0; j < i; j++) {
                int[] last = cuboids[j];
                if (last[0] >= item[0] && last[1] >= item[1] && last[2] >= item[2] ) {
                    h = Math.max(h, arr[j]);
                }
            }
            arr[i] = h + item[2];
            max = Math.max(max, arr[i]);
        }
        return max;
    }

}
